package beusoft.ccjk.com.calculator.sort;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Random;

/**
 * 基数排序
 * Created by CCJK on 2017/12/19.
 */

public class BaseSort {

    private List<Queue<Integer>> list;

    public static void main(String... args) {
        BaseSort sort = new BaseSort();
        int arr[] = new int[10];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(1000);
        }
        sort.println("origin: ");
        sort.printArr(arr);
        sort.sort(arr);
        sort.println("\nsorted:");
        sort.printArr(arr);

    }

    private void printArr(int arr[]) {
        print("[");
        for (int i = 0; i < arr.length; i++) {
            if(i==arr.length-1){
                print(arr[i]);
            }else {
                print(arr[i]+" , ");
            }

        }
        print("]");
    }

    public BaseSort() {
        list = new ArrayList<>();
        for (int i = 0; i < 10; i++) {
            list.add(new LinkedList<Integer>());
        }
    }

    public void sort(int arr[]) {
        int maxPosition = getDigitMaxPosition(max(arr));
        int position = 1;
        do {
            sort(arr, position);
            mapToArr(arr);
            position *= 10;
        } while (position <= maxPosition);

    }

    private void mapToArr(int arr[]) {
        int index = 0;
        for (int i = 0; i < list.size(); i++) {
            Queue<Integer> queue = list.get(i);
            while (!queue.isEmpty()) {
                arr[index++] = queue.poll();
            }
        }
    }

    /**
     * @param position 个位： 1，十位：10， 百位：100 。。。
     * @param arr
     * @param position
     * @return 是否拍完顺序
     */
    private void sort(int arr[], int position) {
        clear();
        for (int i = 0; i < arr.length; i++) {
            int value = getDigitPositionValue(arr[i], position);
            list.get(value).offer(arr[i]);

        }
    }

    /**
     * 取得数字个位，十位，。。。。的值
     *
     * @param digit
     * @param position
     * @return
     */
    private int getDigitPositionValue(int digit, int position) {

        return (digit / position) % 10;

    }

    private int getDigitMaxPosition(int digit) {
        int position = 1;
        while (digit / 10 > 0) {
            position *= 10;
            digit /= 10;
        }
        return position;
    }

    private int max(int arr[]) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) max = arr[i];
        }
        return max;
    }


    private void clear() {
        for (Queue<Integer> queue : list)
            queue.clear();
    }

    private void println(Object o) {
        System.out.println(o);
    }

    private void print(Object o) {
        System.out.print(" " + o);
    }
}
